#ifndef _BIT_DEQUE_H_
#define _BIT_DEQUE_H_

//#include "Kmer.h"
#include <memory>
#include <cassert>

class CompressedKmer;
class KmerVertex;

class BitDeque {
private:
	unsigned char* data;
	unsigned int start;
	unsigned int end;
	unsigned int m_capacity;
public:
	explicit BitDeque(unsigned int initCapacity = 16): data(new unsigned char[initCapacity]),
		start(0), end(0), m_capacity(initCapacity) { memset(data, 0, initCapacity); }

	~BitDeque() {
		delete[] data;
	}

	void initialize(const CompressedKmer& kmer)
	{
		assert(m_capacity >= ((KmerVertex::getLength() + 4) >> 2));
		memcpy(data, kmer.bases, (KmerVertex::getLength() + 4) >> 2);
		start = 0;
		end = KmerVertex::getLength();
	}

	void push_back(unsigned char ele) {
		if (needExpand()) { expand(); }
		data[end >> 2] |= ele << ((3 - (end & 3)) << 1);
		end = (end + 1) % (m_capacity << 2);
	}
	void push_front(unsigned char ele) {
		if (needExpand()) { expand(); }
		start = ((m_capacity << 2) + start - 1) % (m_capacity << 2);
		data[start >> 2] |= ele << ((3 - (start & 3)) << 1);
	}

	/**
	 *
	 * @param src 
	 * @param first 
	 * @param exlast the position just exceed the last element to copy
	 */
	void push_front_range(const BitDeque& src, unsigned int first, unsigned int exlast)
	{
		unsigned newSize = exlast - first + size();
		if (newSize + 1 > (m_capacity << 3)) {
			expand((newSize + 4) >> 2);
		}
		for (; first < exlast;) {
			push_front(src[--exlast]);
		}
	}

	/**
	 *
	 * @param src 
	 * @param first 
	 * @param exlast the position just exceed the last element to copy
	 */
	void push_back_range(const BitDeque& src, unsigned int first, unsigned int exlast)
	{
		unsigned newSize = exlast - first + size();
		if (newSize + 1 > (m_capacity << 3)) {
			expand((newSize + 4) >> 2);
		}
		for (; first < exlast; ++first) {
			push_back(src[first]);
		}
	}

	unsigned int size() const { return ((m_capacity << 2) + end - start) % (m_capacity << 2); }
	unsigned int capacity() const{ return (m_capacity << 2) - 1; }
	bool isEmpty() const { return start == end; }

	void clear() {
		memset(data, 0, m_capacity);
		start = 0;
		end = 0;
	}

	void expand(unsigned int newCapacity) {
		if (newCapacity <= m_capacity) { return; }
		unsigned char* newData = new unsigned char[newCapacity];
		memset(newData, 0, newCapacity);

		if (start <= end) {
			memcpy(newData, data, m_capacity);
		} else {
			memcpy(newData, data, 1 + (end >> 2));
			newData[end >> 2] &= -1 << ((3 - (end & 3)) << 1);
			unsigned int newStart = start + (newCapacity << 2) - (m_capacity << 2);
			memcpy(newData + (newStart >> 2), data + (start >> 2), m_capacity - (start >> 2));
			newData[newStart >> 2] &= ~(-1 << ((4 - (newStart & 3)) << 1));
			start = newStart;
		}
		m_capacity = newCapacity;
		delete[] data;
		data = newData;
	}

	unsigned char operator[](unsigned int pos) const {
		assert(pos >= 0 && pos < size());
		pos = (pos + start) % (m_capacity << 2);
		return (data[pos >> 2] >> ((3 - (pos & 3)) << 1)) & 3;
	}
private:
	bool needExpand() { return ((m_capacity << 2) + end + 1 - start) % (m_capacity << 2) == 0; }
	void expand() {
		expand(m_capacity << 1);
	}
};

#endif